题目

题目背景

小TY的同学HF也想创作艺术

HF只有一块长条状的画布(画条)，所以每一次涂色只能涂上连续几个单位的颜料，同样新的颜料可以完全覆盖旧的颜料

由于他的颜料同样非常傲娇，每次涂完要等上1day才能完全干，只有旧颜料干了以后才能用新颜料覆盖

现在小HF用了2017个年头终于画出了一个大作品，自己非常满意

现在他想复制这份作品

题目描述

Having become bored with standard 2-dimensional artwork (and also frustrated at others copying her work), the great bovine artist Picowso has decided to switch to a more minimalist, 1-dimensional style.

Although, her paintings can now be described by a 1-dimensional array of colors of length NN (1 \leq N \leq 100,0001≤N≤100,000), her painting style remains unchanged: she starts with a blank canvas and layers upon it a sequence of “rectangles” of paint, which in this 1-dimensional case are simply intervals. She uses each of the colors 1 \ldots N1…N exactly once, although just as before, some colors might end up being completely covered up by the end.

To Picowso’s great dismay, her competitor Moonet seems to have figured out how to copy even these 1-dimensional paintings, using a similar strategy to the preceding problem: Moonet will paint a set of disjoint intervals, wait for them to dry, then paint another set of disjoint intervals, and so on. Moonet can only paint at most one interval of each color over the entire process. Please compute

the number of such rounds needed for Moonet to copy a given 1-dimensional Picowso painting.

现在给你一个长度为N(N≤1e5)的画条

上面有若干种颜色，每位的数字表示一种颜色，0表示没有涂色

为了快捷，每次涂色可以用一种颜色填充一个区间，同一种颜色只能使用一次

每次可以涂色好几次，但是这些区间必须分别连续切两两不能相交

然后等待1day油漆干了后再同样操作，输出创作完成并全干了后的最少时间

输入输出格式

输入格式：

The first line of input contains NN, and the next NN lines contain an integer in the range 0 \ldots N0…N indicating the color of each cell in the 1-dimensional painting (0 for a blank cell).

第一行为N，画条长度

一下N行每行一个数表示颜色

输出格式：

Please output the minimum number of rounds needed to copy this painting, or -1 if this could not have possibly been an authentic work of Picowso (i.e., if she could not have painted it using a layered sequence of intervals, one of each color).

输出一个整数表示最少天数。数据若不合法则输出-1

输入输出样例

输入样例#1：

7
0
1
4
5
1
3
3

输出样例#1：

说明

In this example, the interval of color 1 must be painted in an earlier round than the intervals of colors 4 and 5, so at least two rounds are needed.

样例解释：

第一次可以把1颜色和3颜色填充，变成

0 1 1 1 1 3 3

等待1Day后再填充颜色4和颜色5，变成

0 1 4 5 1 3 3

在等待一Day油漆干了后创作完成

所以答案是2

感谢 @ Night_Aurora 贡献翻译

题解

一道大水题（容易想得太复杂了），一种颜色只能用一次，而且必须连续涂，那么被分开来的就一定是被其他颜色覆盖了的，而这段“其他颜色”又可以被覆盖，而且颜色块不能相交（例如0 1 2 1 2就是非法的），我们的问题就转化成了，最大有多少层嵌套的问题。
我们可以从前往后扫，用栈纪录当前层的颜色。

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=100005;
int l[MAXN],r[MAXN];//某种颜色的开始点和结束点
int zhan[MAXN],p;//当前层的颜色
int a[MAXN],ans;//第i个位置的颜色
int tmp;//其实可以不用它，它一直和p相等
 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!l[a[i]])l[a[i]]=i;
        r[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            if(p){//如果0被夹在两个相同颜色块里面，肯定不合法
                cout<<-1;
                return 0;
            }
            else continue;
        }
        if(l[a[i]]==i){//该点是某种颜色的起始点
            if(p&&r[a[zhan[p]]]<r[a[i]]){//上面说到的交叉的情况，没这段会错一个点
                cout<<-1;
                return 0;
            }
            zhan[++p]=i;//入栈
            tmp++;
            ans=max(ans,tmp); //更新答案
        }
        if(r[a[i]]==i){//到了结束点，出栈
            tmp--;
            p--;
        }
    }
    cout<<ans;
    return 0;
}